package leetcode;

/**
 * @Classname CanJump_0055
 * @Author happytaohaha
 * @Date 2020/3/24
 * @Description 55. 跳跃游戏  O(N)   从后往前走
 */
public class CanJump_0055 {


        public boolean canJump(int[] nums) {
            int lastPos = nums.length - 1;
            for (int i = nums.length - 1; i >= 0; i--) {
                if (i + nums[i] >= lastPos) {
                    lastPos = i;
                }
            }
            return lastPos == 0;
        }
    enum Index {
        GOOD, BAD, UNKNOWN
    }

    /**
     * 自底向上
     * @param nums
     * @return
     */
        public boolean canJump2(int[] nums) {
            Index[] memo = new Index[nums.length];
            for (int i = 0; i < memo.length; i++) {
                memo[i] = Index.UNKNOWN;
            }
            memo[memo.length - 1] = Index.GOOD;

            for (int i = nums.length - 2; i >= 0; i--) {
                int furthestJump = Math.min(i + nums[i], nums.length - 1);
                for (int j = i + 1; j <= furthestJump; j++) {
                    if (memo[j] == Index.GOOD) {
                        memo[i] = Index.GOOD;
                        break;
                    }
                }
            }

            return memo[0] == Index.GOOD;
        }



}
